Binary tree paths

Time: O(NxH); Space: O(H); easy

Given a binary tree, return all root-to-leaf paths.

Note:

  • A leaf is a node with no children.

Example 1:

  1
 / \
2   3
 \
  5

Input: root = {TreeNode} [1,2,3,None,5]

Output: [“1->2->5”, “1->3”]

Explanation:

  • All root-to-leaf paths are: 1->2->5, 1->3

Example 2:

  1
 /
2

Input：root = {TreeNode} [1,2]

Output：[“1->2”]

[4]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[5]:

class Solution1(object):
    """
    Time: O(N*H)
    Space: O(H)
    """
    def binaryTreePaths(self, root):
        """
        :type root: {TreeNode}
        :rtype: str
        """
        result, path = [], []
        self.binaryTreePathsRecu(root, path, result)
        return result

    def binaryTreePathsRecu(self, node, path, result):
        if node is None:
            return

        if node.left is node.right is None:
            ans = ''
            for n in path:
                ans += str(n.val) + "->"
            result.append(ans + str(node.val))

        if node.left:
            path.append(node)
            self.binaryTreePathsRecu(node.left, path, result)
            path.pop()

        if node.right:
            path.append(node)
            self.binaryTreePathsRecu(node.right, path, result)
            path.pop()

[6]:

s = Solution1()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
assert s.binaryTreePaths(root) == ["1->2->5", "1->3"]

root = TreeNode(1)
root.left = TreeNode(2)
assert s.binaryTreePaths(root) == ["1->2"]